package com.my.algorithmlearning.leetcode;

import java.util.Arrays;

/**
 * @ClassName Medium_238_ProductOfArrayExceptSelf
 * @Description 优秀题解：https://leetcode.cn/problems/product-of-array-except-self/solutions/11472/product-of-array-except-self-shang-san-jiao-xia-sa/?envType=featured-list&envId=2cktkvj
 * @Author wanghaiwei
 * @Date 2023/7/14 10:28
 */
public class Medium_238_ProductOfArrayExceptSelf {
    public int[] productExceptSelfWithDivision(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int[] result = new int[nums.length];
        int totalProduct = 1;
        int totalProductWithoutZero = 1;
        int zeroCount = 0;
        for (int i = 0; i < nums.length; i++) {
            totalProductWithoutZero *= nums[i] == 0 ? 1 : nums[i];
            zeroCount += nums[i] == 0 ? 1 : 0;
            totalProduct *= nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0 && zeroCount <= 1) {
                result[i] = totalProductWithoutZero;
            } else if (nums[i] == 0 && zeroCount > 1) {
                result[i] = 0;
            } else {
                result[i] = totalProduct / nums[i];
            }
        }
        return result;
    }

    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int[] result = new int[nums.length];
        //下三角矩阵乘积
        int lowerTriangularProduct = 1;
        //上三角矩阵乘积
        int upperTriangularProduct = 1;
        //先计算下三角矩阵
        for (int i = 0; i < nums.length; i++) {
            result[i] = lowerTriangularProduct;
            lowerTriangularProduct *= nums[i];
        }
        //再计算上三角矩阵
        for (int i = nums.length - 1; i > 0; i--) {
            upperTriangularProduct *= nums[i];
            result[i - 1] *= upperTriangularProduct;
        }
        return result;
    }

    public static void main(String[] args) {
        Medium_238_ProductOfArrayExceptSelf solution = new Medium_238_ProductOfArrayExceptSelf();
        int[] result = solution.productExceptSelf(new int[]{1, 2, 3, 4});
        System.out.printf("Input: nums = [1,2,3,4]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{0, 0});
        System.out.printf("Input: nums = [0,0]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{1, 0});
        System.out.printf("Input: nums = [1,0]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{0, 1});
        System.out.printf("Input: nums = [0,1]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{1, 0, 1});
        System.out.printf("Input: nums = [1,0,1]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{1, 0, 1, 0});
        System.out.printf("Input: nums = [1,0,1,0]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{1, 0, 1, 0, 1});
        System.out.printf("Input: nums = [1,0,1,0,1]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{1, 0, 1, 0, 1, 0});
        System.out.printf("Input: nums = [1,0,1,0,1,0]，输出结果：%s \n", Arrays.toString(result));
        result = solution.productExceptSelf(new int[]{1, 0, 1, 0, 1, 0, 1});
        System.out.printf("Input: nums = [1,0,1,0,1,0,1]，输出结果：%s \n", Arrays.toString(result));
    }
}
